class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), l = 0, r = n - 1, l_max = height[l], r_max = height[r], ans = 0;
        while(l < r)
        {
            if(l_max < r_max)
            {
                if(l + 1 < n && l_max > height[l + 1]) ans += l_max - height[l + 1];
                else l_max = height[l + 1];
                ++l;
            }
            else
            {
                if(r > 0 && r_max > height[r - 1]) ans += r_max - height[r - 1];
                else r_max = height[r - 1];
                --r;
            }
        }
        return ans;
    }
};